package leetcode.code5992;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

//执行用时：148 ms, 在所有 Java 提交中击败了100.00%的用户
//
//内存消耗：46.4 MB, 在所有 Java 提交中击败了100.00%的用户
//
//通过测试用例：82 / 82
public class Solution implements IDebug {

	public int maximumGood(int[][] statements) {
		int n = statements.length;
		int max = 0;
		Map<String, Integer> hash = new HashMap<>();
		for (int i = 0; i < n; i++) {
			max = Math.max(max, this.f(i, statements, n, 0, 0, 0, 0, hash));
		}
		return max;
	}

	private int f(int good, int[][] statements, int n, int goods, int gnum, int bads, int bnum,
			Map<String, Integer> hash) {
		String cur = (goods | (1 << good)) + " " + bads;
		if (hash.containsKey(cur)) {
			return hash.get(cur);
		}
		Group group = new Group(n, good, goods, bads, gnum, bnum);
		Queue<Integer> q = new LinkedList<>();
		q.add(good);
		int seen = goods | bads | (1 << good);
		while (!q.isEmpty()) {
			int curGood = q.poll();
			int[] represents = statements[curGood];
			for (int i = 0; i < n; i++) {
				if (!group.checkAdd(i, represents[i])) {
					hash.put(cur, gnum);
					return gnum;
				}
				if (represents[i] == 1 && (seen & (1 << i)) == 0) {
					q.add(i);
					seen |= (1 << i);
				}
			}
		}
		int max = group.goodNum;
		if (n - group.goodNum - group.badNum != 0) {
			for (int i = 0; i < n; i++) {
				if (group.undefine(i)) {
					max = Math.max(max,
							this.f(i, statements, n, group.goods, group.goodNum, group.bads, group.badNum, hash));
				}
			}
		}
		hash.put(cur, max);
		return max;
	}

	class Group {
		int goods;
		int bads;
		int goodNum;
		int badNum;
		int n;

		public Group(int n, int good, int goods, int bads, int gnum, int bnum) {
			this.n = n;
			this.goods = goods;
			this.bads = bads;
			this.setGood(good);
			this.goodNum = gnum + 1;
			this.badNum = bnum;
		}

		public boolean undefine(int personi) {
			int person = 1 << personi;
			if ((this.goods & person) == 0 && (this.bads & person) == 0) {
				return true;
			}
			return false;
		}

		private boolean isGood(int personi) {
			return (this.goods & (1 << personi)) > 0;
		}

		private void setGood(int personi) {
			this.goods |= (1 << personi);
		}

		private boolean isBad(int personi) {
			return (this.bads & (1 << personi)) > 0;
		}

		private void setBad(int personi) {
			this.bads |= (1 << personi);
		}

		public Boolean checkAdd(int personi, int statement) {
			// 2 表示 i 没有对 personi 作出陈述。
			if (statement == 2) {
				return true;
			}
			// 1 表示 i 的陈述认为 personi 是 好人 。
			if (statement == 1) {
				if (this.isGood(personi)) {
					return true;
				} else if (this.isBad(personi)) {
					return false;
				}
				goodNum++;
				this.setGood(personi);
				return true;
			}
			// 0 表示 i 的陈述认为 personi 是 坏人 。
			if (statement == 0) {
				if (this.isGood(personi)) {
					return false;
				} else if (this.isBad(personi)) {
					return true;
				}
				badNum++;
				this.setBad(personi);
				return true;
			}
			return null;
		}
	}

	@Override
	public void debug1() {
		HelpDebug.compare(1, this.maximumGood(HelpDebug.str2array1("[[2,0],[0,2]]")));

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub
		HelpDebug.compare(2, this.maximumGood(HelpDebug.str2array1("[[2,1,2],[1,2,2],[2,0,2]]")));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub
		HelpDebug.compare(3, this.maximumGood(HelpDebug.str2array1("[[2,1,2,2],[1,2,2,2],[2,0,2,2],[2,2,2,2]]")));

	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub
		HelpDebug.compare(2, this.maximumGood(HelpDebug.str2array1("[[2,0,2],[0,2,2],[0,2,2]]")));

	}

	public void debug5() {
		// TODO Auto-generated method stub
		HelpDebug.compare(2, this.maximumGood(
				HelpDebug.str2array1("[[2,0,2,1,2,1],[2,2,2,1,2,0],[2,0,2,1,2,0],[2,1,2,2,2,0],[2,0,2,1,2,0],[2,0,2,1,2,2]]")));

	}

	public void debug6() {
		// TODO Auto-generated method stub
		HelpDebug.compare(1, this.maximumGood(HelpDebug.str2array1("[[2,2,1],[2,2,0],[2,1,2]]")));

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug3();
		so.debug1();
		so.debug2();
		so.debug4();
		so.debug5();
		so.debug6();
	}

}
